package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-preorder-traversal/">二叉树的前序遍历(Binary Tree Preorder Traversal)</a>
 * <p>给你二叉树的根节点 root ，返回它节点值的<b>前序</b>遍历。</p>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,2,3]
 *      输出：[1,2,3]
 *
 * 示例 2：
 *      输入：root = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：root = [1]
 *      输出：[1]
 *
 * 示例 4：
 *      输入：root = [1,2]
 *      输出：[1,2]
 *
 * 示例 5：
 *      输入：root = [1,null,2]
 *      输出：[1,2]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [0, 100] 内</li>
 *     <li>-100 <= Node.val <= 100</li>
 * </ul>
 * <b>进阶：递归算法很简单，你可以通过迭代算法完成吗？</b>
 *
 * @author c2b
 * @see LC0094BinaryTreeInorderTraversal_S 二叉树的中序遍历
 * @see LC0144BinaryTreePreorderTraversal_S 二叉树的前序遍历
 * @see LC0145BinaryTreePostorderTraversal_S 二叉树的后序遍历
 * @since 2023/5/12 9:59
 */
public class LC0144BinaryTreePreorderTraversal_S {

    public List<Integer> preorderTraversal(TreeNode root) {
        return preorderTraversalByIteration(root);
        //return preorderTraversalByRecursion(root);
    }

    private List<Integer> preorderTraversalByRecursion(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorderTraversalByRecursion(root, res);
        return res;
    }

    private void preorderTraversalByRecursion(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorderTraversalByRecursion(root.left, res);
        preorderTraversalByRecursion(root.right, res);
    }

    private List<Integer> preorderTraversalByIteration(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            TreeNode currNode = queue.removeLast();
            res.add(currNode.val);
            if (currNode.right != null) {
                queue.addLast(currNode.right);
            }
            if (currNode.left != null) {
                queue.addLast(currNode.left);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.right = new TreeNode(2);
        node.right.left = new TreeNode(3);

        LC0144BinaryTreePreorderTraversal_S lc0144PreorderTraversal_s = new LC0144BinaryTreePreorderTraversal_S();
        for (Integer integer : lc0144PreorderTraversal_s.preorderTraversal(node)) {
            System.out.println(integer);
        }
    }
}
